Field
The disclosed and claimed concept relates generally to data processing systems and, more particularly, to a data compression and decompression system that is usable as part of a wireless data communication apparatus.
Related Art
Most computerized systems employ the communication of data from one location to another in order to perform operations. Within a computer, the communication of data typically occurs across a data bus, such as when data is communicated between a processor and a storage. It is also well known to wirelessly communicate data from one location to another separate location using any of a wide variety of data protocols.
In nearly all applications, the bandwidth of data communication is limited by one or more constraints. Wireless data communication systems are notoriously subject to such bandwidth limitations. A number of methodologies have been developed to alleviate the effects of such bandwidth limitations that are applicable both in wireless and in wired applications. One solution has involved data compression and subsequent decompression wherein data is compressed using any of a variety of data compression algorithms. Compressed data is then wirelessly transmitted as one or more data packets to another location where the data packets are then decompressed to obtain the original data content. While such data compression/decompression methodologies and systems have been generally effective for their intended purposes, they have not been without limitation.
Several commonly used data compression/decompression methodologies involve comparing a stream of data with previously-communicated streams of data in order to find target strings of data elements that are identical to previously-sent reference strings of data elements. If such an identity is found, the target string of data that otherwise would be transmitted is instead simply replaced with a reference to the reference data string. In order to make such a system work, however, it is typically necessary to maintain a history of past data transmissions or a “dictionary” on both the compression side and the decompression side in order to store previously-communicated data. This enables the decompression algorithm to find the previously-communicated reference string on the decompression side and to replace the communicated reference to that reference string with the previously-communicated reference string itself. Limitations have been encountered, however, with the use of such a dictionary because data storage capabilities typically are limited, and the “dictionary” on each of the compression and decompression sides must likewise be even further limited. Moreover, the sending of a compressed data packet does not always mean that the data packet is received on the decompression side. Such data packets have been known to be lost or delivered out of sequence, and increasing the size of the “dictionary” on the compression and/or decompression sides is not always practical or even possible.
Some attempts have been made to overcome the shortcomings known in the relevant art. Such attempts have included completely erasing the dictionaries on the compression and decompression sides in the event of a lost or delayed data packet. Other solutions have involved the use of a history vector that is at the beginning of each packet, but the transmission overhead required to communicate such a vector increases linearly with the size of the history buffer that is used, which makes this method somewhat inefficient in certain circumstances. It thus would be desirable to provide a solution that overcomes certain shortcomings in the relevant art.